package com.wyp168.leetcode.listnode;

/**
 * @ClassName IsPalindrome
 * @Description TODO
 * @Author wyp168
 * @Date 2022/6/22 20:49
 */
public class IsPalindrome {
    public static void main(String[] args) {
        ListNode ln1 = new ListNode(1);
        ListNode ln2 = new ListNode(3);
        ListNode ln3 = new ListNode(5);
        ListNode ln4 = new ListNode(5);
        ListNode ln5 = new ListNode(3);
        ListNode ln6 = new ListNode(1);
        ln1.next = ln2;
        ln2.next = ln3;
        ln3.next = ln4;
        ln4.next = ln5;
        ln5.next = ln6;
        System.out.println(isPalindrome(ln1));
    }

    /**
     * @description: 判断是否为回文链表
     * @author wyp168
     * @date: 2022/6/22 20:49
     */
    public static boolean isPalindrome(ListNode head) {
        /**
         * 基本思路：
         *  先判断该链表节点数是奇数还是偶数，然后在将后一半的节点反转，然后与前一半节点进行比对
         */
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow =slow.next;
        }

        //判断链表长度是奇数还是偶数
        //是奇数的话，slow节点应该往后移一位，不需要匹配最中间的节点
        if (fast != null) { //说明是偶数
            slow = slow.next;
        }

        //将后面的元素反转
        ListNode reverse = reverse(slow);

        while (reverse != null) {
            if (reverse.val == head.val) {
                reverse = reverse.next;
                head = head.next;
            } else {
                break;
            }
        }

        if (reverse != null) {
            return false;
        } else {
            return true;
        }

    }

    /**
     * 链表反转的方法
     * @param head 传入的链表头节点
     * @return
     */
    public static ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null ) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}
